package com.heima.datastructure.queue;

import java.util.Iterator;

/**
 * <h3>用环形数组实现队列，方法一：tail指针占一个位置</h3>
 *
 * @param <E>
 */
public class ArrayQueue1<E> implements Queue<E>, Iterable<E> {
    // 1、大小为length环形数组中从某个索引cur的位置向前走step步后的索引为(cur + step) % length
    // 2、这种实现方式下，头指针指向队列的头元素，尾指针指向尾元素的下一个元素，所以尾指针会占用环
    //    形数组中的一个元素，实际用来存放队列的只有length - 1个元素，队列为空则head == tail，队
    //    列为满则(tail + 1) % length == head

    private E[] arr; // 环形数组
    private int head; // 头指针，指向头元素
    private int tail; // 尾指针，指向尾元素的下一个元素

    /**
     * 通过构造方法初始化数组以及头尾指针
     *
     * @param capacity 数组的容量
     */
    @SuppressWarnings("all")
    public ArrayQueue1(int capacity) {
        arr = (E[]) new Object[capacity + 1]; // 尾指针会占用一个位置
        head = 0;
        tail = 0;
    }

    /**
     * 向队列尾部插入值
     *
     * @param value 待插入值
     * @return 插入成功返回true，不成功false
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        arr[tail] = value;
        tail = (tail + 1) % arr.length;
        return true;
    }

    /**
     * 获取队列头元素的值，并删除，如果头元素为空，则返回null
     *
     * @return 头元素的值
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = arr[head];
        // 如果是基本类型，不用释放，例如int初始化为0还是四个字节，
        // 但是这里用了泛型，未来会被具体的对象替代，数组里面存的指针（对象的地址），
        // 指针指向这个对象，属于引用类型，该数组元素指向一个对象实例，
        // 当对象实例没有人指向它时才会被垃圾回收，所以这里要去掉指向该对象实例的指针
        arr[head] = null;
        head = (head + 1) % arr.length;
        return value;
    }

    /**
     * 获取队列头元素的值，如果头元素不存在，返回null
     *
     * @return 头元素的值
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return arr[head];
    }

    /**
     * 判断是否为空
     *
     * @return 为空返回true
     */
    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    /**
     * 判断是否为满
     *
     * @return 为满返回true
     */
    @Override
    public boolean isFull() {
        return (tail + 1) % arr.length == head;
    }

    /**
     * 迭代器
     *
     * @return
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int i = head;

            @Override
            public boolean hasNext() {
                return i != tail;
            }

            @Override
            public E next() {
                int index = i;
                i = (i + 1) % arr.length;
                return arr[index];
            }
        };
    }

    /**
     * 获取队列大小
     * @return 队列大小
     */
    public int size(){
        return tail > head ? tail - head : arr.length + tail - head;
    }

    /**
     * 扩容
     * @param capacity
     */
    @SuppressWarnings("all")
    public void expansion(int capacity) {
        if (capacity < arr.length){
            throw new IllegalArgumentException("参数 [" + capacity + "] 不能比" + arr.length + "小");
        }
        E[] array = (E[]) new Object[capacity + 1]; // tail会占一个元素
        // 因为新数组肯定比原数组大，所以直接搬过来从索引零开始赋值
        int j = 0;
        for (int i = head; i != tail; i = (i + 1) % arr.length){
            array[j] = arr[i];
            j++;
        }
        // 重新设置头尾指针以及数组
        head = 0;
        tail = j;
        arr = array; // 实际上是引用，让arr指向array指向的数组对象，即现在arr和array指向同一个数组对象，而arr以前的数组对象没有变量指向它
    }
}
